//给定一个整数数组
// prices，其中第 prices[i] 表示第 i 天的股票价格 。 
//
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 
//
// 
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 
// 
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 
//
// 
//
// 示例 1: 
//
// 
//输入: prices = [1,2,3,0,2]
//输出: 3 
//解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 
//
// 示例 2: 
//
// 
//输入: prices = [1]
//输出: 0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= prices.length <= 5000 
// 0 <= prices[i] <= 1000 
// 
//
// Related Topics 数组 动态规划 👍 1593 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2023-10-05 00:25:48
 * @description 309.买卖股票的最佳时机含冷冻期
 */
public class BestTimeToBuyAndSellStockWithCooldown{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new BestTimeToBuyAndSellStockWithCooldown().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*两种状态*/
    public int maxProfit(int[] prices) {
		int n = prices.length;
		if(n==1) return 0;
		//只用持有和不会持有两种状态
		int [][] dp=new int[n][2];
		//第1天持有
		dp[0][0]=-prices[0];
		//第二天持有
		dp[1][0]=Math.max(-prices[0],-prices[1]);
		//第二天卖出，
		dp[1][1]=Math.max(0,prices[1]-prices[0]);
		//然后从第三天开始考虑，有冷冻期就-2天
		for (int i = 2; i < n; i++) {
			//第i天持有=前一天也持有，或者前前一天才卖今天买
			dp[i][0]=Math.max(dp[i-1][0],dp[i-2][1]-prices[i]);
			//第i天不持有，等于前一天也不持有，或者前前一天买了今天卖
			dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);
		}
		return dp[n-1][1];
	}

	/*三种状态
	* dp[i][0]持有
	* dp[i][1]不持有但在冷冻
	* dp[i][2]不持有不在冷冻*/
	public int maxProfit1(int[] prices) {
		if(prices.length==0) return 0;
		int n=prices.length;
		int [][] dp=new int[n][3];
		dp[0][0]=-prices[0];
		for (int i = 1; i < n; i++) {
			dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
			dp[i][1]=dp[i][0]+prices[i];
			dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]);
		}
		return Math.max(dp[n-1][1],dp[n-1][2]);
	}
	/*空间优化*/
	public int maxProfit2(int[] prices) {
		if(prices.length==0) return 0;
		int n=prices.length;
		int dp0=-prices[0];
		int dp1=0;
		int dp2=0;
		for (int i = 1; i < n; i++) {
			int newdp0=Math.max(dp0,dp2-prices[i]);
			int newdp1=dp0+prices[i];
			int newdp2=Math.max(dp1,dp2);
			dp0=newdp0;
			dp1=newdp1;
			dp2=newdp2;
		}
		return Math.max(dp1,dp2);
	}

	/*递归+记忆化搜索*/
	private int[] prices;
	private int[][] memo;

	public int maxProfit3(int[] prices) {
		this.prices = prices;
		int n = prices.length;
		memo = new int[n][2];
		for (int i = 0; i < n; i++)
			Arrays.fill(memo[i], -1); // -1 表示还没有计算过
		return dfs(n - 1, 0);
	}

	private int dfs(int i, int hold) {
		if (i < 0) return hold == 1 ? Integer.MIN_VALUE : 0;
		if (memo[i][hold] != -1) return memo[i][hold];
		//如果当前持有，递归计算前一天也持有或者前前一天冷冻期今天买
		if (hold == 1)
			return memo[i][hold] = Math.max(dfs(i - 1, 1), dfs(i - 2, 0) - prices[i]);
		//如果不持有，递归计算，前一天也不持有，或者前前一天持有今天卖出
		return memo[i][hold] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
	}
	/*翻译成递推*/
	public int maxProfit4(int[] prices) {
		int n = prices.length;
		//防止越界
		int[][] f = new int[n + 2][2];
		f[1][1] = Integer.MIN_VALUE;
		for (int i = 0; i < n; ++i) {
			f[i + 2][0] = Math.max(f[i + 1][0], f[i + 1][1] + prices[i]);
			f[i + 2][1] = Math.max(f[i + 1][1], f[i][0] - prices[i]);
		}
		return f[n + 1][0];
	}
	/*空间优化*/
	public int maxProfit5(int[] prices) {
		int pre0 = 0, f0 = 0, f1 = Integer.MIN_VALUE;
		//pre0记录前前一天未持有的状态，即冷冻期
		for (int p : prices) {
			int newF0 = Math.max(f0, f1 + p); // f[i+2][0]
			f1 = Math.max(f1, pre0 - p); // f[i+2][1]
			pre0 = f0;
			f0 = newF0;
		}
		return f0;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
